// 子集和模m计数问题
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int main() {
  // 输入：n为数组大小，m为模数
  int n, m;
  cin >> n >> m;

  vector<int> a(n);
  for (int i = 0; i < n; ++i)
    cin >> a[i];

  // 枚举函数：计算区间[l, r)内所有子集的和模m的结果
  auto enumerate = [&](int l, int r) {
    // last: 上一轮迭代的所有可能子集和（不包含当前元素）
    // curr: 当前轮迭代的所有可能子集和（包含当前元素）
    vector<int> last = {0}, curr = {0}; // 初始化为空子集的和0

    // 逐个处理区间内的每个元素
    for (int i = l; i < r; ++i) {
      // nxt: 下一轮迭代的结果，初始化为当前结果（不包含新元素的情况）
      vector<int> nxt = curr;

      // 对于last中的每个子集和，加上当前元素后取模，结果加入nxt
      for (int sum : last)
        nxt.push_back((sum + a[i]) % m);

      // 使用swap更新变量，避免深拷贝，提高性能
      // last变为当前结果（为下一轮做准备）
      // curr变为下一轮结果（包含新元素的所有可能）
      swap(last, curr);
      swap(curr, nxt);
    }
    return curr; // 返回所有可能的子集和模m结果
  };

  ll total_count = 0; // 最终答案：满足条件的子集对数量
  int mid = n / 2;    // 数组中间位置，用于分治

  // 处理两种情况：包含中间元素和不包含中间元素
  for (int include_mid = 0; include_mid < 2; ++include_mid) {
    // 枚举左半部分：从0到mid（可能排除中间元素）
    auto left_sums = enumerate(0, mid - include_mid);
    // 枚举右半部分：从mid+1到n（可能排除中间元素）
    auto right_sums = enumerate(mid + 1 + include_mid, n);

    // 对右半部分结果排序，便于二分查找
    sort(right_sums.begin(), right_sums.end());

    // 遍历左半部分的每个子集和
    for (int left_sum : left_sums) {
      // 如果包含中间元素，则加上中间元素的值
      if (include_mid) {
        left_sum = (left_sum + a[mid]) % m;
      }

      // 计算需要在右半部分查找的目标值
      // 目标：left_sum + right_sum ≡ 0 (mod m)
      // 即 right_sum ≡ -left_sum (mod m)
      int target = (m - left_sum) % m;

      // 使用二分查找统计右半部分中等于target的元素数量
      auto lower = lower_bound(right_sums.begin(), right_sums.end(), target);
      auto upper = upper_bound(right_sums.begin(), right_sums.end(), target);
      total_count += (upper - lower);
    }
  }

  // 输出满足条件的子集对总数
  cout << total_count << '\n';

  return 0;
}